package lc.q201_250;

import java.lang.reflect.Array;
import java.util.Arrays;

public class Q238 {

    public int[] productExceptSelf2(int[] nums) {
        int n = nums.length;
        int[] result = new int[n];
        result[0] = 1;
        for (int i = 1; i < n; i++) {
            result[i] = result[i - 1] * nums[i -1];
        }
        int cur = 1;
        for (int i = n - 1; i >= 0; i--) {
            result[i] = result[i] * cur;
            cur = cur * nums[i];
        }
        return result;
    }


    public int[] productExceptSelf(int[] nums) {
        // 前缀积数组
        int[] preG = new int[nums.length];
        // afterG可以不需要
        int[] afterG = new int[nums.length];
        preG[0] = 1;
        afterG[nums.length - 1] = 1;
        for (int i = 1; i < nums.length; i++) {
            preG[i] = preG[i - 1] * nums[i - 1];
            afterG[nums.length - i - 1] = afterG[nums.length - i] * nums[nums.length - i];
        }
        int[] result = new int[nums.length];
        for (int i = 0; i < result.length; i++) {
            result[i] = preG[i] * afterG[i];
        }
        return result;
    }

    public static void main(String[] args) {
        Q238 q238 = new Q238();
        int[] ints = q238.productExceptSelf2(new int[]{1, 2, 3, 4, 5});
        System.out.println(Arrays.toString(ints));
    }

}
